import com.sun.source.tree.Tree;

//二叉搜索树
public class BinarySearchTree {
    /*
    静态内部类定义节点
     */
    static class TreeNode{
        public int val;//值
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子

        //构造函数
        public TreeNode(int val){
            this.val=val;
        }
    }
    //当前搜索树的根节点
    public TreeNode root=null;


    /*
    二叉搜索树的查找
    时间复杂度:
    最优情况下：二叉搜索树为完全二叉树，平均比较次数：树的高度O(logN)
    最差情况下：是单分支的单支树，平均比较次数N：O(N)
     */
    public TreeNode search (int val){
        TreeNode cur=root;
        while(cur!=null){
            if(val>cur.val){
                cur=cur.right;
            }else if(val<cur.val){
                cur=cur.left;
            }else{
                return cur;
            }
        }
        //到这里来了说明cur==null
        return null;
    }


    /*
    二叉搜索树的插入
     */
    public void insert(int val) {
        TreeNode newNode = new TreeNode(val);//首先将传入的这个val值变成一个节点
        if (root == null) {//根为空即树为空，直接插入
            root = newNode;
            return;
        }
        //到这里来了说明树不为空，要按照查找逻辑确定插入位置，插入新节点
        TreeNode cur = root;
        TreeNode parent = cur;
        while (cur != null) {
            if (val > cur.val) {//往右走
                parent = cur;//要先写它；因为这里会写parent=cur所以上面定义parent的时候可以parent=null
                cur = cur.right;
            } else if (val < cur.val) {//往左走
                parent = cur;
                cur = cur.left;
            } else {//有相等的，就不用插入l
                return;
            }
        }
        //走到这里，说明cur为空了，那么parent.left或parent.right为新节点newNode
//不能这样if if(parent.left==null){
//            parent.left=newNode;
//         }else{
//            parent.right=newNode;
//         }
        if(parent.val<val){
            parent.right=newNode;
        }else{
            parent.left=newNode;
        }
    }


    /*
    二叉搜索树的删除
     */
    public void remove(int val){
        TreeNode cur=root;
        TreeNode parent=root;//这里不能parent=null，因为要是root即为要删除的那个节点的话，直接进入removeNode，而parent=null，则parent.left=cur.right、parent.right=cur.right
                             //会出现空指针异常--》错，如果root即为要删除的那个节点的话根本没有parent.left=cur.right、parent.right=cur.right这两项操作，所以可以parent=null
        while(cur!=null){
            if(val>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(val<cur.val){
                parent=cur;
                cur=cur.left;
            }else{//相等的话就删除
                removeNode(cur,parent);
                return;
            }
        }
    }
    private void removeNode(TreeNode cur, TreeNode parent) {
        //a.cur.left==null
        if(cur.left==null){
            if(cur==root){//1.cur==root
                root=cur.right;
                //return;可有可无
            }else if(cur==parent.left){//2.cur是一个左孩子
                parent.left=cur.right;
            }else{//2.cur是一个右孩子
                parent.right=cur.right;
            }
        }else if(cur.right==null){//b.cur.right==null
            if(cur==root){//1.cur==root
                root=cur.left;
                //return;可有可无
            }else if(cur==parent.left){//2.cur是一个左孩子
                parent.left=cur.left;
            }else{//2.cur是一个右孩子
                parent.right=cur.left;
            }
        }else {//c.cur.left!=null&&cur.right!=null--替换法
            TreeNode target=cur.right;
            TreeNode targetParent=cur;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            //走到这里target为null，即target没有左孩子了，那么target就是cur右树中最左边的节点
            cur.val=target.val;
            if(target==targetParent.left){//如果target是targetParent的左孩子
                targetParent.left=target.right;
            }else{//如果target是targetParent的右孩子
                targetParent.right=target.right;
            }
        }/*
           只有一个根节点的情况，包含在了cur.left==null这里面，所以就不用单独讨论了

           else if(cur.left!=null&&cur.right!=null)这个情况要用替换法进行删除，要删除cur：
           1.在cur的右树中找最左边的节点t，使cur.val=t.val，删除t（为什么这样可以？因为cur要比cur右树里的节点都小，所以要替换的话，应该找个最小值放在cur的位置）
           2.在cur的左树中找最右边的节点t，使cur.val=t.val，删除t（为什么这样可以？因为cur要比cur左树里的节点都大，所以要替换的话，应该找个最大值放在cur的位置）
         */
    }
}

/*
teac:
public class BinarySearchTree {

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //当前搜索树的根节点
    public TreeNode root = null;

    public TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

    public void insert(int val) {
        TreeNode newNode = new TreeNode(val);
        if(root == null) {
            root = newNode;
            return;
        }

        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else {
                return;
            }
        }
        if(parent.val < val) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
    }


    public void remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else {
                removeNode(cur,parent);
                return;
            }
        }
    }

    private void removeNode(TreeNode cur, TreeNode parent) {
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                //if(cur == parent.right)
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            //10分上课
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }
}

 */